package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Backtracking;
import cn.pugle.oj.catalog.BitProblem;

import java.util.*;

/**
 * _1上小改, 去掉path, 使用神奇的bit操作
 * <p>
 * Runtime: 5 ms, faster than 87.93% of Java online submissions for Sudoku Solver.
 * <p>
 * 和下面这个有很多相似之处, 当然大佬的更精妙
 * https://leetcode.com/problems/sudoku-solver/discuss/15796/Singapore-prime-minister-Lee-Hsien-Loong's-Sudoku-Solver-code-runs-in-1ms
 *
 * @author tzp
 * @since 2020/10/26
 */
public class LC37_2 implements Backtracking, BitProblem {
    char[] dict = new char[]{'1', '2', '3', '4', '5', '6', '7', '8', '9'};
    char empty = '.';

    int[] row = new int[9];
    int[] col = new int[9];
    int[] grid = new int[9];
    boolean hasResult = false;
    char[][] board;
    int cnt = 0;//调试用, 递归次数4208

    public void solveSudoku(char[][] board) {
        this.board = board;
        int x = -1, y = -1, v = 0;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != empty) {
                    set(i, j, board[i][j]);
                    v++;
                } else {
                    if (x == -1) {
                        x = i;
                        y = j;
                    }
                }
            }
        }
        backtracing(x, y, v);
        System.out.println(cnt);
    }

    public void backtracing(int x, int y, int validNum) {//tzpdo 不按模板来啊这个回溯
        cnt++;
        for (int i = 0; i < dict.length; i++) {//先为当前格子选择数字
            char choice = dict[i];
            if (validSudoku(x, y, choice)) {
                //根据大佬的Possibles = Block[InBlock[Square]] & Row[InRow[Square]] & Col[InCol[Square]];
                //既然已经用了row/col/grid三个bit位了, 可以直接找出可选的值, 根本不用循环9次!!
                set(x, y, choice);
                if (validNum == 80) {
                    hasResult = true;
                    return;
                }
                int index = x * 9 + y;
                for (int j = index + 1; j < 81; j++) {
                    int newX = j / 9;
                    int newY = j % 9;
                    if (board[newX][newY] == empty) {
                        backtracing(newX, newY, validNum + 1);
                        if (hasResult) {
                            return;
                        }
                        break;
                    }
                }
                unset(x, y, choice);
            }
        }
    }

    public boolean validSudoku(int x, int y, char c) {
        int gridIndex = (x / 3) * 3 + (y / 3);
        return (row[x] & (1 << ((int) c - '1'))) == 0
                && (col[y] & (1 << ((int) c - '1'))) == 0
                && (grid[gridIndex] & (1 << ((int) c - '1'))) == 0;
    }

    public void set(int x, int y, char c) {
        board[x][y] = c;
        int gridIndex = (x / 3) * 3 + (y / 3);
        row[x] |= 1 << ((int) c - '1');
        col[y] |= 1 << ((int) c - '1');
        grid[gridIndex] |= 1 << ((int) c - '1');
    }

    public void unset(int x, int y, char c) {
        board[x][y] = empty;
        int gridIndex = (x / 3) * 3 + (y / 3);
        row[x] &= ~(1 << ((int) c - '1'));
        col[y] &= ~(1 << ((int) c - '1'));
        grid[gridIndex] &= ~(1 << ((int) c - '1'));
    }

    public static void main(String[] args) {
        char[][] b = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
        new LC37_2().solveSudoku(b);
        System.out.println(Arrays.deepToString(b));
    }
}
